package leetcode.year2021.month11;

//581. 最短无序连续子数组
public class _11_2FindUnsortedSubarray581 {
  public static int findUnsortedSubarray(int[] nums) {
    // 解法二： 从左往右遍历，维护一个最大值 求取right指针
    // 解法二： 从右往左遍历，维护一个最小值 求取left指针
    int n = nums.length;


    int left = -1;
    int right = -1;

    int leftMax = Integer.MIN_VALUE;
    int rightMin = Integer.MAX_VALUE;

    for (int i = 0; i < n; i++) {
      if (nums[i] >= leftMax ){
        leftMax = nums[i];
      } else {
        right = i;
      }
      if (nums[n-1-i] <= rightMin){
        rightMin = nums[n-1-i];
      } else {
        left = n-1-i;
      }
    }

    return right == -1 ? 0 : right-left+1;
  }
//  // 三次遍历，第一次遍历求得每个元素左边的最大值，第二次遍历求得每个元素右边的最小值
//  // 然后双指针从两边开始，左右遇到第一个不满足条件的，则停止
//  public static void main(String[] args) {
//    int[] ints = {1, 3, 2, 2, 2};
//    findUnsortedSubarray(ints);
//  }
//
//  public static int findUnsortedSubarray(int[] nums) {
//    int length = nums.length;
//    // 求取每个值左边的最大值
//    int[] leftMax = new int[length];
//    int leftMaxNum = Integer.MIN_VALUE;
//    leftMax[0] = leftMaxNum;
//    for (int i = 1; i < length; i++) {
//      leftMax[i] = Math.max(nums[i-1],leftMaxNum);
//    }
//
//    // 求取每个值右边的最小值
//    int[] rightMin = new int[length];
//    int rightMinNum = Integer.MAX_VALUE;
//    rightMin[length-1] = rightMinNum;
//    for (int i = length-2; i >= 0; i--) {
//      rightMinNum = Math.min(nums[i+1],rightMinNum);
//      rightMin[i] = rightMinNum;
//    }
//
//    // 双指针，从两边开始往里走，判断当前值是否左边都小于等于自己，右边都大于等于自己。
//    int leftPoint = 0;
//    int rightPoint = length-1;
//
//    while (leftPoint >= 0 && leftPoint < length && nums[leftPoint] >= leftMax[leftPoint] && nums[leftPoint] <= rightMin[leftPoint]){
//      leftPoint++;
//    }
//
//    while (rightPoint >= 0 && rightPoint < length && nums[rightPoint] >= leftMax[rightPoint] && nums[rightPoint] <= rightMin[rightPoint] && rightPoint>=leftPoint){
//      rightPoint--;
//    }
//
//    return rightPoint - leftPoint + 1;
//  }

  /**
   * 581. 最短无序连续子数组
   * 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
   *
   * 请你找出符合题意的 最短 子数组，并输出它的长度。
   *
   *
   *
   * 示例 1：
   *
   * 输入：nums = [2,6,4,8,10,9,15]
   * 输出：5
   * 解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
   * 示例 2：
   *
   * 输入：nums = [1,2,3,4]
   * 输出：0
   * 示例 3：
   *
   * 输入：nums = [1]
   * 输出：0
   *
   *
   * 提示：
   *
   * 1 <= nums.length <= 104
   * -105 <= nums[i] <= 105
   *
   *
   * 进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
   */
}
